#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//struct ListNode* EntryNodeOfLoop(struct ListNode* pHead) {
//    // write code here
//    if (pHead == NULL)
//    {
//        return NULL;
//    }
//
//    struct ListNode* p1 = pHead;
//    struct ListNode* p2 = pHead;
//    int n = 0;
//    while (1)
//    {
//        if (p2->next == NULL || p2 == NULL)
//        {
//            return NULL;
//        }
//        p1 = p1->next;
//        p2 = p2->next;
//        p2 = p2->next;
//        n++;
//        if (p1 == p2)
//        {
//            struct ListNode* p3 = pHead;
//            if (n % 2 == 0)
//            {
//                n /= 2;
//            }
//            else {
//                n = (n + 1) / 2;
//            }
//            while (n--)
//            {
//                p3 = p3->next;
//            }
//            return p3;
//        }
//    }
//}

//struct RandomListNode* Clone(struct RandomListNode* pHead) {
//    // write code here
//    if (pHead == NULL)
//    {
//        return NULL;
//    }
//    struct RandomListNode* p = pHead;
//    while (p)
//    {
//        struct RandomListNode* ph = (struct RandomListNode*)malloc(sizeof(struct RandomListNode));
//        ph->random = NULL;
//        ph->label = p->label;
//        ph->next = p->next;
//        p->next = ph;
//        p = ph->next;
//    }
//    p = pHead;
//    struct RandomListNode* newnode = p->next;
//    struct RandomListNode* pp = newnode;
//    while (p)
//    {
//        if (p->random == NULL)
//        {
//            newnode->random = NULL;
//        }
//        else
//        {
//            newnode->random = p->random->next;
//        }
//        p->next = newnode->next;
//        p = p->next;
//        if (p == NULL)
//        {
//            break;
//        }
//        newnode->next = p->next;
//        newnode = newnode->next;
//    }
//    return pp;
//}

//struct ListNode* deleteDuplication(struct ListNode* pHead) {
//    // write code here
//    struct ListNode* p1 = pHead;
//    struct ListNode* p5 = p1;
//    struct ListNode* p4 = p1;
//    while (p1)
//    {
//        int k = 1;
//        struct ListNode* p2 = p1->next;
//        struct ListNode* p3 = p1;
//        while (p2)
//        {
//            if (p1->val == p2->val)
//            {
//                k = 0;
//                p3->next = p2->next;
//                free(p2);
//                p2 = p3->next;
//            }
//            else
//            {
//                p2 = p2->next;
//                p3 = p3->next;
//            }
//        }
//        if (k == 0)
//        {
//            if (p1 == p5)
//            {
//                p5 = p1->next;
//                p1 = p1->next;
//                free(p4);
//                p4 = p1;
//            }
//            else
//            {
//                p4->next = p1->next;
//                free(p1);
//                p1 = p4->next;
//            }
//        }
//        if (k == 1)
//        {
//            p4 = p1;
//            p1 = p1->next;
//        }
//    }
//    return p5;
//}

//struct ListNode* deleteNode(struct ListNode* head, int val) {
//    // write code here
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    struct ListNode* p1 = head;
//    struct ListNode* p2 = head;
//    struct ListNode* p3 = head;
//    while (p1)
//    {
//        if (p1->val == val)
//        {
//            if (p1 == p2)
//            {
//                p2 = p1->next;
//                free(p1);
//                p1 = p2;
//                p3 = p2;
//            }
//            else
//            {
//                p3->next = p1->next;
//                free(p1);
//                p1 = p3->next;
//            }
//        }
//        else
//        {
//            p3 = p1;
//            p1 = p1->next;
//        }
//    }
//    return p2;
//}


//struct RandomListNode* Clone(struct RandomListNode* pHead) {
//    // write code here
//    if (pHead == NULL)
//    {
//        return NULL;
//    }
//    struct RandomListNode* p = pHead;
//    while (p)
//    {
//        struct RandomListNode* ph = (struct RandomListNode*)malloc(sizeof(struct RandomListNode));
//        ph->random = NULL;
//        ph->label = p->label;
//        ph->next = p->next;
//        p->next = ph;
//        p = ph->next;
//    }
//    p = pHead;
//    struct RandomListNode* newnode = p->next;
//    while (p)
//    {
//        if (p->random == NULL)
//        {
//            newnode->random = NULL;
//        }
//        else
//        {
//            newnode->random = p->random->next;
//        }
//        p = newnode->next;
//        if (p == NULL)
//        {
//            break;
//        }
//        newnode = p->next;
//    }
//    p = pHead;
//    newnode = p->next;
//    struct RandomListNode* pp = newnode;
//    while (p)
//    {
//        p->next = newnode->next;
//        p = p->next;
//        if (p == NULL)
//        {
//            break;
//        }
//        newnode->next = p->next;
//        newnode = newnode->next;
//    }
//    return pp;
//}


//struct ListNode* EntryNodeOfLoop(struct ListNode* pHead) {
//    // write code here
//    if (pHead == NULL || pHead->next == NULL)
//    {
//        return NULL;
//    }
//    if (pHead->next == pHead)
//    {
//        return pHead;
//    }
//    struct ListNode* p1 = pHead;
//    struct ListNode* p2 = pHead;
//    while (p1 && p2)
//    {
//        p1 = p1->next;
//        p2 = p2->next->next;
//        if (p1 == p2)
//        {
//            struct ListNode* p3 = pHead;
//            while (p1 != p3)
//            {
//                p1 = p1->next;
//                p3 = p3->next;
//            }
//            return p1;
//        }
//    }
//    return NULL;
//}

//int GetNumberOfK(int* data, int dataLen, int k) {
//    // write code here
//    int i = 0;
//    int num = 0;
//    for (i = 0; i < dataLen; i++)
//    {
//        if (data[i] == k)
//        {
//            num++;
//        }
//    }
//    return num;
//}

//int minNumberInRotateArray(int* rotateArray, int rotateArrayLen) {
//    // write code here
//    int min = rotateArray[0];
//    int n = 0;
//    for (n = 0; n < rotateArrayLen; n++)
//    {
//        if (rotateArray[n] < min)
//        {
//            min = rotateArray[n];
//        }
//    }
//    return min;
//}


//int* multiply(int* A, int ALen, int* returnSize) {
//    // write code here
//    int BLen = ALen;
//    int* B = (int*)malloc(sizeof(int) * ALen);
//    int AL = 0;
//    int BL = 0;
//    for (BL = 0; BL < BLen; BL++)
//    {
//        int sum = 1;
//        for (AL = 0; AL < ALen; AL++)
//        {
//            if (AL == BL)
//            {
//                continue;
//            }
//            sum *= A[AL];
//        }
//        B[BL] = sum;
//    }
//    *returnSize = BLen;
//    return B;
//}

//int FirstNotRepeatingChar(char* str) {
//    // write code here
//    int arr[127] = { 0 };
//    int i = 0;
//    int sz = strlen(str);
//    for (i = 0; i < sz; i++)
//    {
//        if (arr[(int)str[i]] == 0)
//        {
//            arr[(int)str[i]] = 1;
//        }
//        else
//        {
//            arr[(int)str[i]]++;
//        }
//    }
//    for (i = 0; i < sz; i++)
//    {
//        if (arr[(int)str[i]] == 1)
//        {
//            return i;
//        }
//    }
//    return -1;
//}